package 力扣.比赛;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 单线程CPU_1834 {
    //短作业优先：贪心
    public int[] getOrder(int[][] tasks) {
        if (tasks == null || tasks.length == 0){
            return new int[]{};
        }
        int len1 = tasks.length;
        PriorityQueue<Tas> pq = new PriorityQueue<>(//选择短作业执行，如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行
                (t1,t2) ->{//小根堆
                        return t1.ints[1] == t2.ints[1] ? t1.index - t2.index : t1.ints[1] - t2.ints[1];
                }
        );
        Tas[] tasInts = new Tas[len1];
        for (int i = 0; i < len1; i++) {
             tasInts[i] = new Tas(i,tasks[i]);//带索引的数组
        }
        Arrays.sort(tasInts,(Tas t1, Tas t2) ->{
            if (t1.ints[0] == t2.ints[0]){
                return t1.ints[1] - t2.ints[1];
            }else {
                return t1.ints[0] - t2.ints[0];
            }
        });
        int timeStamp = tasInts[0].ints[0];//第一个
//        pq.add(tasInts[0]);
        int[] ans = new int[len1];
        int o = 0;
        int i = 0;
        for (; i < len1; i++) {
            if (tasInts[i].ints[0] <= timeStamp){
                pq.add(tasInts[i]);
            }else break;
        }
        while (!pq.isEmpty()){
            Tas t = pq.poll();
            ans[o++] = t.index;
            if (timeStamp < t.ints[0]){//CPU空转
                timeStamp = t.ints[0];
            }
            timeStamp += t.ints[1];//执行之后
            for (; i < len1; i++) {
                if (tasInts[i].ints[0] <= timeStamp){
                    pq.add(tasInts[i]);
                }else break;
            }
            if (pq.isEmpty() && i < len1){//处理队列为空，但是还是有任务的情况
                pq.add(tasInts[i++]);
            }
        }
        return ans;

    }
    class Tas{
        private int index;
        private int[] ints;
        public Tas(){}
        public Tas(int index, int[] ints) {
            this.index = index;
            this.ints = ints;
        }
    }

    public int[] getOrder3(int[][] tasks) {
        if (tasks == null || tasks.length == 0){
              return new int[0];
        }
        final int N = tasks.length;
        Tas[] tas = new Tas[N];
        for (int i = 0; i < N; i++) {//设置下标和数组
            tas[i] = new Tas(i,tasks[i]);
        }
        //从小到大排序，如果时间相同，则选择短作业
        Arrays.sort(tas,
                (Tas t1, Tas t2) ->{
                    if (t1.ints[0] == t2.ints[0]){
                        return t1.ints[1] - t2.ints[1];
                    }else {
                        return t1.ints[0] - t2.ints[0];
                    }
                });
        PriorityQueue<Tas> pq = new PriorityQueue<>(
                ((o1, o2) -> {//短作业优先，如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
                    if (o1.ints[1] == o2.ints[1]){
                        return o1.index - o2.index;
                    }else {
                        return o1.ints[1] - o2.ints[1];
                    }
                })
        );
        //CPU开始运行，通过时间戳
        //将第一组任务加入队列
        int timeStamp = tas[0].ints[0];
        int i = 0;
        for (; i < N; i++) {
             if (tas[i].ints[0] > timeStamp){
                 break;
             }
             pq.add(tas[i]);
        }
        int[] ans = new int[N];
        int pos = 0;
        //执行全部任务
        while (!pq.isEmpty()){
            Tas tas1 = pq.poll();
            ans[pos++] = tas1.index;
            timeStamp = Math.max(timeStamp, tas1.ints[0]);
            timeStamp += tas1.ints[1];

            for (; i < N; i++) {
                if (tas[i].ints[0] > timeStamp){
                    break;
                }
                pq.add(tas[i]);
            }
            if (pq.isEmpty() && i < N){
               pq.add(tas[i++]);
            }
        }
        return ans;
    }
}
